375D - Tree and Queries - CodeForces Solution

//https://codeforces.com/contest/375/problem/D
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define PI acos(-1)
#define LSB(i) ((i) & -(i))
#define ll int
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define sc second
#define th third
#define fo fourth
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ldb double
#define INF 1e15
#define MOD 1000000007
#define endl "\n"

#define all(data)       data.begin(),data.end()
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define TYPEMIN(type)   std::numeric_limits<type>::min()
#define MAXN 200007
vector<ll> adj[MAXN];
ll c[MAXN],pera,sz[MAXN],pos[MAXN],timer,col[MAXN],cnt[MAXN],cntk[MAXN],rez[MAXN];
struct dd
{
    ll l,r,k,idx;
} qry[MAXN];
bool cmp(dd x,dd y)
{
    if(x.l/pera!=y.l/pera) return x.l/pera<y.l/pera;
    else return x.r<y.r;
}
void DFS(ll i,ll p)
{
    sz[i]=1; pos[i]=++timer; col[timer]=c[i];
    for(auto j:adj[i])
    {
        if(j==p) continue;
        DFS(j,i); sz[i]+=sz[j];
    }
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    ll n,m,a,b,v,k,l=1,r=0; cin>>n>>m; pera=ceil(sqrt(n));
    for(int i=1;i<=n;i++) cin>>c[i];
    for(int i=1;i<n;i++)
    {
        cin>>a>>b;
        adj[a].pb(b); adj[b].pb(a);
    }
    DFS(1,0);
    for(int i=1;i<=m;i++)
    {
        cin>>v>>k;
        qry[i].idx=i; qry[i].k=k; qry[i].l=pos[v]; qry[i].r=pos[v]+sz[v]-1;
    }
    sort(qry+1,qry+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        while(r<qry[i].r) cntk[++cnt[col[++r]]]++;
        while(r>qry[i].r) cntk[cnt[col[r--]]--]--;
        while(l<qry[i].l) cntk[cnt[col[l++]]--]--;
        while(l>qry[i].l) cntk[++cnt[col[--l]]]++;
        rez[qry[i].idx]=cntk[qry[i].k];
    }
    for(int i=1;i<=m;i++) cout<<rez[i]<<endl;
    return 0;
}